package ChessEngine;

import iodevice.CommandPhalanx;
import iodevice.Kdoparser;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Timer;
import java.util.TimerTask;

import ChessEngine.moveGenerator.MoveGenerator;
import ChessEngine.moveGenerator.Exceptions.BoardException;
import boardData.Board;

/**
 * Implementiert eine Alpha Beta Suche. Dies bedeutet, dass Teilbäume mit bei
 * denen feststeht das sie eine schlechtere Bewertung als die bereits beste
 * gefundene Bewertung haben werden nicht weiter verfolgt.
 * 
 * @author daniel
 * 
 */
public class AlphaBeta extends AbstractSearch {

	private String bestMove = "";
	private int bestEval = 0;
	private int actualSearchDepth;
	private GameTree tree;
	private SearchThread searcher;
	private HashMap<Integer, TranspositionTableEntry> transPosTable;

	public AlphaBeta() {
		actualSearchDepth = 0;
		// tree = new GameTree();
		// transPosTable = new HashMap<Integer, TranspositionTableEntry>();
	}

	@Override
	public boolean stopSearching() {
		// suche wird von außen beendet, timer anhalten und interrupt flag
		// setzten
		searcher.interruptTimer.cancel();
		searcher.interrupt();
		String[] result = new String[2];
		result[0] = "move";
		CommandPhalanx.info("Interrupted, Bester Zug: " + bestMove);
		result[1] = bestMove;
		Kdoparser.giveOrder(result);
		return searcher.isInterrupted();
	}

	@Override
	public String calculateNextMove(Board b, boolean white, long millisToCalc)
			throws BoardException {
		/*
		 * Es sollte nicht fuer jede Suche ein neuer Spielbaum aufgebaut werden,
		 * der alte kann genutzt werden.
		 */
		// final long boardHash = b.hashCode();
		// TranspositionTableEntry entry = transpositionTable.get(boardHash
		// % HASH_TABLE_SIZE);
		// if (entry != null && entry.getZobristHash() == boardHash) {
		// // wir haben diese Stellung schonmal durchsucht, der knoten im Baum
		// // muss als root gesetzt werden.
		// Node newRoot = null;
		// for (Node child : tree.getRoot().getList()) {
		// if (child.getBoardData().hashCode() == boardHash) {
		// newRoot = child;
		// }
		// }
		// if (newRoot != null) {
		// tree.setRootNode(b, b.isSideWhite());
		// }else{
		// //TODO LOG;
		// tree = new GameTree(b,b.isSideWhite());
		// }
		// }else{
		// tree = new GameTree(b,b.isSideWhite());
		// }

		searcher = new SearchThread(b, white, millisToCalc, this);
		searcher.start();
		// if (!searcher.isInterrupted()) {
		return bestMove;
		// }
	}

	public String getBestMove() {
		return bestMove;
	}

	/**
	 * Jeder Suchalgorithmus führt die Suche in einem eigenem Thread durch. Dies
	 * hat den Vorteil, dass falls ein Stop Kommando kommt einfach der thread
	 * unterbrochen werden muss. Der Suchalgorithmus bekommt alle notwendigen
	 * informationen (wie z.B. das Board auf dem gesucht werden soll und die
	 * zeit) bei der Erzeugung eines des Objekts übergeben. Um die suche zu
	 * starten muss dann nur noch die start methode aufgerufen werden. Im Laufe
	 * der Suche wird der bisher beste gefundene Zug in der Variablen bestMove
	 * gespeichert. Diese existiert auch noch nachdem der Thread (die Suche)
	 * fertig ist oder oder unterbrochen wurde und kann daher einfach von der
	 * MainEngine abgefragt werden.
	 */
	protected class SearchThread extends Thread {

		// private GameTree tree;
		private MoveGenerator moveGenerator;
		private AbstractEvalutor evaluator;
		private long millisToCalc;
		private AlphaBeta searcher;
		Timer interruptTimer = new Timer();
		private long searchedNodesCount = 0;
		private long timeSearchStarted = 1;

		public SearchThread(Board b, boolean white, long millisToCalc,
				AlphaBeta search) {

			this.moveGenerator = new MoveGenerator();
			this.evaluator = new PieceSquareTableEvaluator();
//			this.evaluator = new PieceSquareSimpleEvaluator();
//			 this.evaluator = new SimpleEvaluator();
			this.millisToCalc = millisToCalc;
			this.searcher = search;
			timeSearchStarted = 1;

			/*
			 * im moment wird für jeden neue Suche ein neuer Spielbaum
			 * aufgebaut. es wäre besser, wenn man jeweils an die ergebnisse der
			 * vorherigen suche anknüfen würde also den Suchbaum nur einmal bei
			 * erzeugug des objekts machen und nur den den neuen teilbaum weiter
			 * durchsuchen...
			 */
			tree = new GameTree();
			tree.setRootNode(b, b.isSideWhite());
		}

		@Override
		public void run() {
			searchedNodesCount = 0;
			timeSearchStarted = System.currentTimeMillis() - 1;
			bestMove = "";
			TimerTask timerTask = new TimerTask() {

				@Override
				public void run() {
					searcher.stopSearching();
				}
			};

			interruptTimer.schedule(timerTask, millisToCalc
					- ((millisToCalc * 5) / 100));

			actualSearchDepth = 0;
			int depth = 1;
			while (depth <= AbstractSearch.SEARCH_DEPTH) {
				// while(!isInterrupted()){
				if (isInterrupted()) {
					CommandPhalanx
							.infoString("Suchthread wurde unterbrochen...SearchThread run");
					return;
				}
				try {
					CommandPhalanx.info("depth " + depth);
					CommandPhalanx.infoString("depth " + depth);
					tree.getRoot().setNodeList(null);
					bestMove = alphaBetaRoot(tree.getRoot(), depth);
					// Kdoparser.giveOrder("move" + bestMove);
					if (bestMove.equals("error")) {
						// TODO Exception log error
						interruptTimer.cancel();
						return;
					}
					CommandPhalanx.infoString("Beste Bewertung bei Tiefe"
							+ depth + ": " + bestMove);
				} catch (BoardException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				depth++;
			}
			interruptTimer.cancel();

			CommandPhalanx.infoString("Suchthread fertig.");
			String[] result = new String[2];
			result[0] = "move";
			// CommandPhalanx.info("Interrupted, Bester Zug: " + bestMove);
			result[1] = bestMove;
			if (!isInterrupted()) {
				Kdoparser.giveOrder(result);
			}

		}

		/**
		 * 
		 * @param node
		 * @param depth
		 * @return
		 * @throws BoardException
		 */
		public String alphaBetaRoot(Node node, int depth) throws BoardException {
			String bestMoveLocal = "";
			int bestEvalLocal=0;
			if (node.getList() == null || node.getList().isEmpty()) {
				LinkedList<Board> possibleMoves = moveGenerator.generateMove(
						node.getBoardData(), node.getBoardData().isSideWhite());

				if (possibleMoves.isEmpty()) {
					CommandPhalanx
							.infoString("Es konnte keine gültige Stellung für diese Position ermittelt werden.");
					return bestMove;
				}
				node.setList(possibleMoves);
			}

			int alpha = Integer.MIN_VALUE;
			int beta = Integer.MAX_VALUE;
			Board bestBoard = null;
			if (node.getList().size() == 1) {
				// falls es nur einen möglichen Zug gibt zurueckgeben und
				// fertig.
				return node.getList().getFirst().getBoardData().getCurrMove();
			}
			int possibleBoards = node.getList().size();
			for (int i = 0; i < possibleBoards; i++) {
				Node n = node.getList().get(0);
				searchedNodesCount++;
				final Double millisSearched = ((double) System
						.currentTimeMillis() - timeSearchStarted);
				long secsSearched = 1;
				if (millisSearched > 1000) {
					secsSearched = (long) (millisSearched / 1000);
				}
				final long nps = searchedNodesCount / secsSearched;
				CommandPhalanx
						.info("nodes " + searchedNodesCount + " nps " + (nps)
								+ " currmove " + n.getBoardData().getCurrMove());
				// CommandPhalanx
				// .infoString("nodes "
				// + searchedNodesCount
				// + " nps "
				// + (searchedNodesCount / Math.round(secsSearched))
				// + " currmove " + n.getBoardData().getCurrMove());
				if (isInterrupted()) {
					CommandPhalanx.infoString("SuchThread wurde unterbrochen");
					return bestMove;
				}
				node.getList().remove(0);
				int val = alphaBeta(n, alpha, beta, depth);
				n.setEvaluation(val);
				if (node.isWhiteMove()) {
					if (val > alpha) {
						alpha = val;
						if (val > bestEvalLocal || bestMoveLocal.equals("")) {
							String newBestMove = n.getBoardData().getCurrMove();
							if(newBestMove!=null) {
								bestMoveLocal = newBestMove;
								bestEvalLocal = n.getEvaluation();
							}
						}
						if (val > bestEval || bestMove.equals("")) {
							String newBestMove = n.getBoardData().getCurrMove();
							if(newBestMove != null) {
								bestMove = newBestMove;
								bestEval = n.getEvaluation();
							}
						}
						
					}
					if(n.getBoardData().getCurrMove().equals(bestMove) && val < bestEval) {
						if(!bestMoveLocal.equals("")) {
							bestMove = bestMoveLocal;
							bestEval = bestEvalLocal;
						}
					}
				} else {
					if (val < beta ) {
						beta = val;
						if (val < bestEvalLocal || bestMoveLocal.equals("")) {
							String newBestMove = n.getBoardData().getCurrMove();
							if(newBestMove != null) {
								bestMoveLocal = newBestMove;
								bestEvalLocal = n.getEvaluation();
							}
						}
						if(val<bestEval || bestMove.equals("")){
							String newBestMove = n.getBoardData().getCurrMove();
							if(newBestMove != null) {
								bestMove = newBestMove;
								bestEval = n.getEvaluation();
							}
						}
					}
					if(n.getBoardData().getCurrMove().equals(bestMove) && val > bestEval) {
						if(!bestMoveLocal.equals("")) {
							bestMove = bestMoveLocal;
							bestEval = bestEvalLocal;
						}
					}
				}

			}
//			final LinkedList<Node> nonNullNodeList = new LinkedList<Node>();
//			for (int i = 0; i < node.getList().size(); i++) {
//				final Node childnode = node.getList().get(i);
//				if (node != null) {
//					nonNullNodeList.add(childnode);
//				}
//			}
//			node.setNodeList(nonNullNodeList);
			return bestMove;
		}

		/**
		 * 
		 * @param node
		 * @param alpha
		 * @param beta
		 * @param depth
		 * @return
		 * @throws BoardException
		 */
		private int alphaBeta(Node node, int alpha, int beta, int depth)
				throws BoardException {
			if (isInterrupted()) {
				CommandPhalanx.infoString("SucheThrad wurde unterbrochen...");
				return -1;
			}
			actualSearchDepth++;
			if (actualSearchDepth == depth) {
				// Blattknoten an Suchtiefe erreicht, Knoten bewerten und
				// Suchtiefe
				// verringern.
				actualSearchDepth--;
				if (node.getEvaluation() == 0) {
					node.setEvaluation(evaluator.evaluate(node.getBoardData()));
				}
				return node.getEvaluation();
			} else {
				if (!(node.hasChildren())) {
					// Suchtiefe noch nicht erreicht und knoten hat keine
					// Kinder,
					// also anhaengen.
					LinkedList<Board> possibleMoves = moveGenerator
							.generateMove(node.getBoardData(), node
									.getBoardData().isSideWhite());
					node.setList(possibleMoves);

				}
			}

			// alle kindknoten durchlaufen
			int possibleBoards = node.getList().size();
			for (int i = 0; i < possibleBoards; i++) {
				Node childNode = node.getList().get(0);
				searchedNodesCount++;
				final Double millisSearched = ((double) System
						.currentTimeMillis() - timeSearchStarted);
				long secsSearched = 1;
				if (millisSearched > 1000) {
					secsSearched = (long) (millisSearched / 1000);
				}
				final long nps = searchedNodesCount / secsSearched;
				CommandPhalanx.info("nodes " + searchedNodesCount + " nps "
						+ (nps));
				// CommandPhalanx
				// .infoString("nodes "
				// + searchedNodesCount
				// + " nps "
				// + ( nps));
				/*
				 * falls ein interrupt gesetzt wurde aufhören...
				 */
				if (isInterrupted()) {
					CommandPhalanx
							.infoString("SucheThrad wurde unterbrochen...");
					return -1;
				}
				/*
				 * stack anlegen und schauen ob aktueller Knoten ein
				 * "guter"knoten ist.(in transposition table) falls nein diesesn
				 * auf dem stack speichern und weiter falls ja knoten
				 */
				node.getList().remove(0);
				if (node.isWhiteMove()) {
					// weiss ist am zug, Bewertung des Aktuellen Knoten
					// ermitteln
					// ist bewertung vlt schon in transposition table vorhanden?

					int subResult = 0;
					subResult = alphaBeta(childNode, alpha, beta, depth);

					alpha = Math.max(alpha, subResult);

					node.setEvaluation(alpha);
					if (alpha >= beta) {
						// hier wird der Baum Abgeschnitten, die knoten aus der
						// liste loeschen, alpha cut
//						int firstNodeToRemove = node.getList().indexOf(
//								childNode);
//						for (int j = node.getList().size() - 1; j > firstNodeToRemove; j--) {
//							node.getList().removeLast();
//						}

						node.cutOff = true;
						actualSearchDepth--;

						return alpha;
					}

				} else {
					// in transposition table nachschauen ob vlt schon bewertet.

					int subResult = alphaBeta(childNode, alpha, beta, depth);

					beta = Math.min(beta, subResult);
					node.setEvaluation(beta);
					if (alpha >= beta) {
						// hier wird der Baum Abgeschnitten, die knoten aus der
						// liste loeschen, beta cut
//						int firstNodeToRemove = node.getList().indexOf(
//								childNode);
//						for (int j = node.getList().size() - 1; j > firstNodeToRemove; j--) {
//							node.getList().removeLast();
//						}
						node.cutOff = true;
						actualSearchDepth--;

						return beta;
					}
				}
			}
//			final LinkedList<Node> nonNullNodeList = new LinkedList<Node>();
//			for (int i = 0; i < node.getList().size(); i++) {
//				final Node childnode = node.getList().get(i);
//				if (node != null) {
//					nonNullNodeList.add(childnode);
//				}
//			}
//			node.setNodeList(nonNullNodeList);
			actualSearchDepth--;

			if (node.isWhiteMove()) {
				return alpha;
			} else {
				return beta;
			}
		}

		public Timer getInterruptTimer() {
			return interruptTimer;
		}

	}
}
